Quantum Circuits for the Unitary Permutation Problem
Identifieur interne : 000534 ( Main/Exploration ); précédent : 000533; suivant : 000535Quantum Circuits for the Unitary Permutation Problem
Auteurs : Stefano Facchini [France] ; Simon Perdrix [France]Source :
Abstract
We consider the Unitary Permutation problem which consists, given $n$ unitary gates $U_1, \ldots, U_n$ and a permutation $\sigma$ of $\{1,\ldots, n\}$, in applying the unitary gates in the order specified by $\sigma$, i.e. in performing $U_{\sigma(n)}\ldots U_{\sigma(1)}$. This problem has been introduced and investigated by Colnaghi et al. where two models of computations are considered. This first is the (standard) model of query complexity: the complexity measure is the number of calls to any of the unitary gates $U_i$ in a quantum circuit which solves the problem. The second model provides quantum switches and treats unitary transformations as inputs of second order. In that case the complexity measure is the number of quantum switches. In their paper, Colnaghi et al. have shown that the problem can be solved within $n^2$ calls in the query model and $\frac{n(n-1)}2$ quantum switches in the new model. We refine these results by proving that $n\log_2(n) +\Theta(n)$ quantum switches are necessary and sufficient to solve this problem, whereas $n^2-2n+4$ calls are sufficient to solve this problem in the standard quantum circuit model. We prove, with an additional assumption on the family of gates used in the circuits, that $n^2-o(n^{7/4+\epsilon})$ queries are required, for any $\epsilon >0$. The upper and lower bounds for the standard quantum circuit model are established by pointing out connections with the permutation as substring problem introduced by Karp.
Url:
DOI: 10.1007/978-3-319-17142-5_28
Affiliations:
- France
- Auvergne-Rhône-Alpes, Rhône-Alpes
- Grenoble
- Université Joseph Fourier, Université Pierre-Mendès-France, Université de Grenoble
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 003E79
- to stream Hal, to step Curation: 003E79
- to stream Hal, to step Checkpoint: 000515
- to stream Main, to step Merge: 000534
- to stream Main, to step Curation: 000534
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Quantum Circuits for the Unitary Permutation Problem</title>
<author><name sortKey="Facchini, Stefano" sort="Facchini, Stefano" uniqKey="Facchini S" first="Stefano" last="Facchini">Stefano Facchini</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-49673" status="VALID"><orgName>CAPP</orgName>
<orgName type="acronym">LIG Laboratoire d'Informatique de Grenoble</orgName>
<desc><address><addrLine>Laboratoire LIG - 110 av. de la Chimie - Domaine Universitaire - BP 53 - 38041 Grenoble - cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://equipes-lig.imag.fr/capp</ref>
</desc>
<listRelation><relation active="#struct-3886" type="direct"></relation>
<relation active="#struct-51016" type="direct"></relation>
<relation active="#struct-300275" type="direct"></relation>
<relation name="UMR5217" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-3886" type="direct"><org type="institution" xml:id="struct-3886" status="OLD"><orgName>Université Pierre Mendès France</orgName>
<orgName type="acronym">Grenoble 2 UPMF</orgName>
<date type="end">2015-12-31</date>
<desc><address><addrLine>BP 47 - 38040 Grenoble Cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.upmf-grenoble.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-51016" type="direct"><org type="institution" xml:id="struct-51016" status="OLD"><orgName>Université Joseph Fourier</orgName>
<orgName type="acronym">UJF</orgName>
<date type="end">2015-12-31</date>
<desc><address><addrLine>BP 53 - 38041 Grenoble Cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.ujf-grenoble.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300275" type="direct"><org type="institution" xml:id="struct-300275" status="VALID"><orgName>Institut National Polytechnique de Grenoble (INPG)</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR5217" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Pierre-Mendès-France</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Joseph Fourier</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
</affiliation>
</author>
<author><name sortKey="Perdrix, Simon" sort="Perdrix, Simon" uniqKey="Perdrix S" first="Simon" last="Perdrix">Simon Perdrix</name>
<affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00994182</idno>
<idno type="halId">hal-00994182</idno>
<idno type="halUri">https://hal.inria.fr/hal-00994182</idno>
<idno type="url">https://hal.inria.fr/hal-00994182</idno>
<idno type="doi">10.1007/978-3-319-17142-5_28</idno>
<date when="2015-05-18">2015-05-18</date>
<idno type="wicri:Area/Hal/Corpus">003E79</idno>
<idno type="wicri:Area/Hal/Curation">003E79</idno>
<idno type="wicri:Area/Hal/Checkpoint">000515</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000515</idno>
<idno type="wicri:Area/Main/Merge">000534</idno>
<idno type="wicri:Area/Main/Curation">000534</idno>
<idno type="wicri:Area/Main/Exploration">000534</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Quantum Circuits for the Unitary Permutation Problem</title>
<author><name sortKey="Facchini, Stefano" sort="Facchini, Stefano" uniqKey="Facchini S" first="Stefano" last="Facchini">Stefano Facchini</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-49673" status="VALID"><orgName>CAPP</orgName>
<orgName type="acronym">LIG Laboratoire d'Informatique de Grenoble</orgName>
<desc><address><addrLine>Laboratoire LIG - 110 av. de la Chimie - Domaine Universitaire - BP 53 - 38041 Grenoble - cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://equipes-lig.imag.fr/capp</ref>
</desc>
<listRelation><relation active="#struct-3886" type="direct"></relation>
<relation active="#struct-51016" type="direct"></relation>
<relation active="#struct-300275" type="direct"></relation>
<relation name="UMR5217" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-3886" type="direct"><org type="institution" xml:id="struct-3886" status="OLD"><orgName>Université Pierre Mendès France</orgName>
<orgName type="acronym">Grenoble 2 UPMF</orgName>
<date type="end">2015-12-31</date>
<desc><address><addrLine>BP 47 - 38040 Grenoble Cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.upmf-grenoble.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-51016" type="direct"><org type="institution" xml:id="struct-51016" status="OLD"><orgName>Université Joseph Fourier</orgName>
<orgName type="acronym">UJF</orgName>
<date type="end">2015-12-31</date>
<desc><address><addrLine>BP 53 - 38041 Grenoble Cedex 9</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.ujf-grenoble.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300275" type="direct"><org type="institution" xml:id="struct-300275" status="VALID"><orgName>Institut National Polytechnique de Grenoble (INPG)</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR5217" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Pierre-Mendès-France</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
<placeName><settlement type="city">Grenoble</settlement>
<region type="region" nuts="2">Auvergne-Rhône-Alpes</region>
<region type="old region" nuts="2">Rhône-Alpes</region>
</placeName>
<orgName type="university">Université Joseph Fourier</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Grenoble</orgName>
</affiliation>
</author>
<author><name sortKey="Perdrix, Simon" sort="Perdrix, Simon" uniqKey="Perdrix S" first="Simon" last="Perdrix">Simon Perdrix</name>
<affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
</analytic>
<idno type="DOI">10.1007/978-3-319-17142-5_28</idno>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We consider the Unitary Permutation problem which consists, given $n$ unitary gates $U_1, \ldots, U_n$ and a permutation $\sigma$ of $\{1,\ldots, n\}$, in applying the unitary gates in the order specified by $\sigma$, i.e. in performing $U_{\sigma(n)}\ldots U_{\sigma(1)}$. This problem has been introduced and investigated by Colnaghi et al. where two models of computations are considered. This first is the (standard) model of query complexity: the complexity measure is the number of calls to any of the unitary gates $U_i$ in a quantum circuit which solves the problem. The second model provides quantum switches and treats unitary transformations as inputs of second order. In that case the complexity measure is the number of quantum switches. In their paper, Colnaghi et al. have shown that the problem can be solved within $n^2$ calls in the query model and $\frac{n(n-1)}2$ quantum switches in the new model. We refine these results by proving that $n\log_2(n) +\Theta(n)$ quantum switches are necessary and sufficient to solve this problem, whereas $n^2-2n+4$ calls are sufficient to solve this problem in the standard quantum circuit model. We prove, with an additional assumption on the family of gates used in the circuits, that $n^2-o(n^{7/4+\epsilon})$ queries are required, for any $\epsilon >0$. The upper and lower bounds for the standard quantum circuit model are established by pointing out connections with the permutation as substring problem introduced by Karp.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
</country>
<region><li>Auvergne-Rhône-Alpes</li>
<li>Rhône-Alpes</li>
</region>
<settlement><li>Grenoble</li>
</settlement>
<orgName><li>Université Joseph Fourier</li>
<li>Université Pierre-Mendès-France</li>
<li>Université de Grenoble</li>
</orgName>
</list>
<tree><country name="France"><region name="Auvergne-Rhône-Alpes"><name sortKey="Facchini, Stefano" sort="Facchini, Stefano" uniqKey="Facchini S" first="Stefano" last="Facchini">Stefano Facchini</name>
</region>
<name sortKey="Perdrix, Simon" sort="Perdrix, Simon" uniqKey="Perdrix S" first="Simon" last="Perdrix">Simon Perdrix</name>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000534 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000534 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Exploration |type= RBID |clé= Hal:hal-00994182 |texte= Quantum Circuits for the Unitary Permutation Problem }}
This area was generated with Dilib version V0.6.33. |